A field programmable device, FPD, (or a so-called "field programmable gate array") is a versatile integrated circuit chip which includes an array of identical logic blocks (herein referred to as macrocells). The internal circuitry of the FPD can be configured by an individual user to realize a user-specific circuit. To configure an FPD, the user configures an on-chip interconnect structure of the FPD (so-called "programming of the FPD") so that selected inputs and outputs of selected macrocells are connected together in such a way that the resulting circuit is the user-specific circuit desired by the user. Given that the programming of FPDs can typically be performed by the end user in minutes, the use of FPDs can result in a dramatic decrease in the turn-around time and cost associated with the design of application-specific integrated circuits.
Several computer-aided design (CAD) systems have been designed to automate the process of implementing ("mapping") logic circuits onto the FPDs of various vendors. Typically, such CAD systems perform a logic optimization step followed by a technology mapping step. During the logic optimization step, the logic circuit, which is typically represented as a graph (called a netlist) whose nodes represent Boolean functions, is simplified through the use of techniques that are independent of the specific FPD on which the circuit is to be implemented. Such techniques include, for example, the removal of common subexpressions.
The technology mapping step determines the interconnections required to implement the netlist produced by the logic optimization step on the target FPD. Some methods used to perform technology mapping involve the covering of the netlist with pattern graphs chosen from a library of pattern graphs, each of which represents a function that can be implemented on one macrocell. Depending on its complexity, the function, may be represented by more than one pattern graph.
Library-based methods perform poorly when applied to complex macrocells. The set of pattern graphs corresponding to functions implementable on a macrocell of sufficient complexity is too large to be entirely stored in the pattern graph library. A library of such size would result in an unacceptably slow technology mapping step for all but the simplest circuits. As a result, the pattern graph library is typically restricted to the pattern graphs for a subset of the functions implementable on a complex macrocell. This results in less dense implementations since clusters of gates in the netlist corresponding to functions not represented in the library of pattern graphs but nevertheless implementable on one macrocell are implemented on two or more macrocells.